lintcode 二进制升序排序

Posted on | In

描述

考虑一个十进制整数数组，我们要根据以下规则重新排列数组：

注意

按二进制表示中的1个数对整数升序排序。
二进制表示中具有相同数量1的元素按照十进制值升序排序。

样例

1

输入：[12, 10, 7, 5, 6]
输出：[5,6,10,12,7]
解释：最初数组[12, 10, 7, 5, 6] = [1100,1010,0111,0101,0110]，最终数组[0101,0110,1010,1100,0111] = [5,6,10,12,7]

2

输入：[7, 8, 6, 5]
输出：[8, 5, 6, 7]
解释：最初数组[7, 8, 6, 5] = [0111, 1000, 0110, 0101]，最终数组[1000, 0101, 0110, 0111] = [8, 5, 6, 7]

思路

将十进制转换为二进制，然后比较字符串，最后sort

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
public:
    /**
     * @param nums: the original integer array
     * @return: the integer array after sorting
     */
    static string Dec2Bin(int tar) {
        string res;
        while (tar != 1 && tar != 0) {
            if(tar%2 == 1)
                res.insert(0,1,'1');
            else
                res.insert(0,1,'0');

            tar /= 2;
        }
        if (tar == 1)
            res.insert(0,1,'1');


        return res;
    } //decimal to binary

    static int Bin2Dec(string tar) {
        int res=0;
        int n = tar.length();

        for (int i = n-1; i >=0; i--)
            if (tar[i] == '1')
                res += pow(2,n-i-1);

        return res;
    }// binary to decimal

    static bool cmp(const int & a, const int & b) {
        string binA = Dec2Bin(a), binB = Dec2Bin(b);
        int na = 0, nb = 0;
        for (int i = 0; i < binA.length(); i++)
            if (binA[i] == '1')
                na++;

        for (int i = 0; i < binB.length(); i++)
            if (binB[i] == '1')
                nb++;

        return na > nb ? false : na < nb ? true : a < b;


    }
    vector<int> AscendingBinarySorting(vector<int> &nums) {
        // Write your code here
        sort(nums.begin(), nums.end(), cmp);
        return nums;
    }
};
-------------end of filethanks for reading-------------